"""
f(n) = f(n-1) + f(n-2)
method1: 
normal recursion 

method2:
dynamic programming

method3:
tail recursion
"""

import pdb
from timeit import timeit


def method1_fibo(n):
    #  pdb.set_trace()
    if not isinstance(n, int) or n < 1:
        raise ValueError("n must be a integer")
    if n == 1 or n == 2:
        return 1

    else:
        return method1_fibo(n - 1) + method1_fibo(n - 2)


def method2_fibo(n):
    if n == 1 or n == 2:
        return 1
    a = 1
    b = 1
    for i in range(n - 2):
        a, b = b, a + b
    return b


def method3_fibo(n, ret1, ret2):
    if n == 1:
        return ret1
    else:
        ret1, ret2 = ret2, ret1 + ret2
        return method3_fibo(n - 1, ret1, ret2)


if __name__ == "__main__":
    n = 600
    #  t1 = timeit(
    #      f"method1_fibo({n})",
    #      "from __main__ import method1_fibo",
    #      number=10000,
    #  )
    #  print(t1)
    t2 = timeit(
        f"method2_fibo({n})",
        "from __main__ import method2_fibo",
        number=10000,
    )
    print(t2)
    t3 = timeit(
        f"method3_fibo({n},1,1)",
        "from __main__ import method3_fibo",
        number=10000,
    )
    print(t3)
